package com.tys.algorithm.advanced.code.class32;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Code04_AC2 {

    // 前缀树的节点
    public static class Node {
        // 如果一个node，end为空，不是结尾，是字符串的沿途节点
        // 如果end不为空，表示这个点是某个字符串的结尾，end的值就是这个字符串
        public String end;
        // 只有在上面的end变量不为空的时候，endUse才有意义
        // 表示，这个字符串之前有没有加入过答案，防止重复收集
        public boolean endUse;
        public Node fail; //每个node都有
        public Node[] nexts;

        public Node() {
            endUse = false;
            end = null;
            fail = null;
            nexts = new Node[26];
        }
    }

    //AC自动机
    public static class ACAutomation {
        //头节点
        private Node root;

        public ACAutomation() {
            //字符放路径上，不是节点上
            root = new Node();
        }

        //加入字符串，不关心fail
        public void insert(String s) {
            char[] str = s.toCharArray();
            Node cur = root;
            int index = 0;
            for (int i = 0; i < str.length; i++) {
                index = str[i] - 'a';
                if (cur.nexts[index] == null) {
                    //没有路新建
                    cur.nexts[index] = new Node();
                }
                //有路复用
                cur = cur.nexts[index];
            }
            cur.end = s;
        }

        //连fail
        public void build() {
            //宽度优先遍历，使用队列
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            Node cur = null;
            Node cfail = null;
            //父节点出来，设置子的fail指针
            while (!queue.isEmpty()) {
                // 某个父亲，cur
                cur = queue.poll();
                for (int i = 0; i < 26; i++) { // 所有的路
                    // cur -> 父亲  i号儿子，必须把i号儿子的fail指针设置好！
                    if (cur.nexts[i] != null) { // 如果真的有i号儿子
                        //先设置fail默认为root，找到再设置为别的
                        cur.nexts[i].fail = root;
                        cfail = cur.fail; //父的fail
                        //寻找子该连谁
                        while (cfail != null) {
                            if (cfail.nexts[i] != null) {
                                //子的fail指向
                                cur.nexts[i].fail = cfail.nexts[i];
                                break;
                            }
                            cfail = cfail.fail;
                        }
                        //子放入队列，继续判断
                        queue.add(cur.nexts[i]);
                    }
                }
            }
        }

        // 大文章：content
        public List<String> containWords(String content) {
            char[] str = content.toCharArray();
            Node cur = root;
            Node follow = null;
            int index = 0;
            List<String> ans = new ArrayList<>();
            for (int i = 0; i < str.length; i++) {
                index = str[i] - 'a'; // 大文章的路
                // 如果当前字符在这条路上没配出来，就随着fail方向走向下条路径
                // 没有index方向的路 && fail指针不是root 失败
                while (cur.nexts[index] == null && cur != root) {
                    //当前指针移动
                    cur = cur.fail;
                }
                // 1) 现在来到的路径，是可以继续匹配的:cur.nexts[index]
                // 2) 现在来到的节点，就是前缀树的根节点:root
                cur = cur.nexts[index] != null ? cur.nexts[index] : root;
                follow = cur;
                //是否有敏感词
                while (follow != root) {
                    //防止重复收集
                    if (follow.endUse) {
                        break;
                    }
                    // 不同的需求，在这一段之间修改
                    if (follow.end != null) {
                        //收集敏感词
                        ans.add(follow.end);
                        follow.endUse = true;
                    }
                    // 不同的需求，在这一段之间修改
                    follow = follow.fail;
                }
            }
            return ans;
        }

    }

    public static void main(String[] args) {
        ACAutomation ac = new ACAutomation();
        ac.insert("dhe");
        ac.insert("he");
        ac.insert("abcdheks");
        // 设置fail指针
        ac.build();

        List<String> contains = ac.containWords("abcdhekskdjfafhasldkflskdjhwqaeruv");
        for (String word : contains) {
            System.out.println(word);
        }
    }

}
